package com.datastructures.hashtable.CuckooHash;

import java.util.Random;

/**
 * 布谷鸟散列
 * @author MaoLin Wang
 * @date 2020/2/1521:25
 */
public class CuckooHashTable<T> {
    private static final double MAX_LOAD=0.4;
    private static final int ALLOWED_REHASHES=1;
    private static final int DEFAULT_TABLE_SIZE=101;

    private final HashFamily<? super T>hashFunctions;
    private final int numHashFunctions;
    private T[] array;
    private int currentSize;

    public CuckooHashTable(HashFamily<? super T> hashFunctions) {
      this(hashFunctions,DEFAULT_TABLE_SIZE);
    }

    public CuckooHashTable(HashFamily<? super T> hashFunctions, int size) {
        allocateArray(nextPrime(size));
        doClear();
        this.hashFunctions = hashFunctions;
        this.numHashFunctions = hashFunctions.getNumberOfFunctions();
    }

    /**
     * 选择合适的散列函数，将它的值按比例对应到一个有效的数组下标
     * @param x
     * @param whitch
     * @return
     */
    private int myhash(T x,int whitch){
        int hashVal = hashFunctions.hash(x, whitch);
        hashVal %= array.length;
        if (hashVal<0)
            hashVal+=array.length;
        return hashVal;
    }

    /**
     * 去查所有散列函数，返回包含x项的数组下标，如果找不到x就返回-1,。
     * @param x
     * @return
     */
    private int findPos(T x){
        for (int i = 0; i < numHashFunctions; i++) {
            int pos=myhash(x,i);
            if (array[pos]!=null && array[pos].equals(x)){
                return pos;
            }
        }
        return -1;

    }
    private boolean contains(T x){
        return findPos(x)!=-1;
    }
    private boolean remove(T x){
        int pos=findPos(x);
        if (pos!=-1){
            array[pos]=null;
            currentSize--;
        }
        return pos!=-1;
    }

    private boolean insert(T x){
        if (contains(x)) {

            return false;
        }
        if (currentSize>=array.length*MAX_LOAD){
            expand();
        }
        return insertHelper1(x);
    }

    private  int rehashes=0;
    private Random r=new Random();
    private boolean insertHelper1(T x) {
        final  int COUNT_LIMIT=100;
        while (true){
            int lastPos=-1;
            int pos;
            for (int count = 0; count < COUNT_LIMIT; count++) {
                for (int i = 0; i < numHashFunctions; i++) {
                     pos = myhash(x, i);
                     if (array[pos] ==null){
                         array[pos]=x;
                         currentSize++;
                         return true;
                     }
                }
                int i=0;
                do {
                    pos=myhash(x,r.nextInt(numHashFunctions));
                }while (pos==lastPos&&i++<5);

                T temp=array[lastPos=pos];
                array[pos]=x;
                x=temp;
            }
            if (++rehashes>ALLOWED_REHASHES){
                expand();
                rehashes=0;
            }else {
                rehash();
            }
        }
    }

    private void rehash() {
        hashFunctions.generateNewFunctions();;
        rehash(array.length);
    }
    private void rehash(int newLength){
        T[] oldArray=array;
        allocateArray( nextPrime(newLength));
        currentSize=0;
        for (T str:oldArray){
            if (str!=null){
                insert(str);
            }
        }
    }

    private void expand() {
        rehash();
    }

    private void allocateArray(int arraySize) {
        array=(T [])new Object[arraySize];
    }

    private int nextPrime(int size) {
        return -1;
    }

    private void doClear(){
        currentSize=0;
        for (int i = 0; i < array.length; i++) {
            array[i]=null;
        }
    }
}
